package com.shuang.tree27;

import java.util.ArrayList;
import java.util.List;

public class BinaryTreePaths {

    //递归(从根节点开始找路径 （前序）) + 回溯
    public List<String> binaryTreePaths(TreeNode root) {

        //用于封装结果
        List<String> result = new ArrayList<>();

        if (root == null) {
            return result;
        }

        //用于记录路径 定义整数集合便于回溯 后续拼接成字符串返回即可
        List<Integer> path = new ArrayList<>();

        //递归函数用于逻辑处理 封装结果
        traversal(root, path, result);

        return result;
    }

    public void traversal(TreeNode root, List<Integer> path, List<String> result) {

        //中
        path.add(root.val);

        //递归终止条件 到叶子节点（该节点的左右孩子为空） 处理路径拼接成字符串返回
        if (root.left == null && root.right == null) {
            StringBuilder sb = new StringBuilder();

            for (int i = 0; i < path.size() - 1; i++){
                sb.append(path.get(i)).append("->");
            }

            //拼接最后一个路径
            sb.append(path.get(path.size() - 1));

            //封装一个路径到结果中去
            result.add(sb.toString());

            return;
        }

        // 递归和回溯是同时进行，所以要放在同一个花括号里
        //左
        if (root.left != null) {
            traversal(root.left, path, result);
            //等待 回溯 移除最后一个元素 相当于回到路径上一个节点处
            path.remove(path.size() - 1);
        }

        //右
        if (root.right != null) { // 右
            traversal(root.right, path, result);
            path.remove(path.size() - 1);// 回溯
        }

    }
}
